package HighMethod06;

/**
 * ClassName:    QuickFindMid
 * Package:    HighMethod06
 * Description:
 * Datetime:    2021/4/18 0018   11:35
 * Author: 沈新源
 */
public class QuickFindMid {


    public static void Print_2Max(int[] br) {
        int max1 = Math.max(br[0], br[1]);
        int max2 = Math.min(br[0], br[1]);

        for (int i = 2; i < br.length; ++i) {
            if (br[i] > max1) {
                max2 = max1;
                max1 = br[i];
            } else if (br[i] > max2) {
                max2 = br[i];
            }
        }

//        int max1 = 0;
//        int max2 = 0;
//        for (int i = 0; i < br.length; i++) {
//            if (br[i] >= max2) {
//                max2 = br[i];
//                if (max2 > max1) {
////                    Swap(max1, max2);   //这样交换不行 JAVA语言没有指针
//                    int tmp = max1;
//                    max1 = max2;
//                    max2 = tmp;
//                }
//            }
//        }
        System.out.printf("max1 : %d max2 ： %d \n", max1, max2);
    }

    private static void Swap(int max1, int max2) {
        Object tmp = max1;
        max1 = max2;
        max2 = (int) tmp;
    }

    public static int Partition(int[] br, int left, int right) {
        int i = left, j = right;
        int tmp = br[i];
        while (i < j) {
            while (i < j && br[j] > tmp) --j;
            if (i < j) br[i] = br[j];
            while (i < j && br[i] <= tmp) ++i;
            if (i < j) br[j] = br[i];
        }
        br[i] = tmp;
        return i;
    }

    //不能解决数据重复的问题   第k小
    public static int Print_K(int[] br, int left, int right, int k) {
        if (left == right && k == 1) return br[left];

        int index = Partition(br, left, right);
        int pos = index - left + 1;

        if (k <= pos) return Print_K(br, left, index, k);
        else return Print_K(br, index + 1, right, k - pos);     //###
    }

    public static int Print_K_Min(int[] br, int k) {
        return Print_K(br, 0, br.length - 1, k);
    }

    //两者中的小者
    public static int Min(int a, int b){
        return Math.min(a,b);
    }
    //三者中的最小者
    public static int Min3(int a,int b,int c){
        return Min(a,Min(b,c));
    }

    //左区域最小值
    public static int MaxS1(int[] br,int left, int right){
        return br[right];
    }
    //有区域最大值
    public static int MinS2(int[] br,int left, int right){
        int mins = br[left];
        for(int i =left+1;i<=right;i++){
            if(mins>br[i]){
                mins = br[i];
            }
        }
        return mins;
    }

    //分治策略
    public static int ComPair(int[] br,int left,int right){
        if(right - left <=0) return Integer.MAX_VALUE;      //返回条件
        int k = (right - left+1)/2;                 //这里的k是相对下标

        Print_K(br,left,right,k);
        int d1 = ComPair(br,left,left+k-1);      //s1区域     物理下标的转换
        int d2 = ComPair(br,left+k,right);      //s2区域

        int maxs1 = MaxS1(br,left,left+k-1);
        int mins2 = MinS2(br,left+k,right);

        return Min3(d1,d2,mins2-maxs1);     //分治策略的汇合

    }

    public static void main(String[] args) {
        int[] ar = {56, 78, 12, 34, 90, 67, 100, 45, 23, 89};
//        int[] ar = {56, 78, 12, 34, 90, 67, 100, 45, 23, 89,100};     //Print_K_Min 会报错？？？？不能存在重复数据

//        Print_2Max(ar);       //输出两个最大的数

        System.out.println("找到第K小！");
        for (int k = 1; k <= ar.length; ++k) {
            System.out.printf("%d => %d \t", k, Print_K_Min(ar, k));
        }

        //测试：最接近点对
//        System.out.println(ComPair(ar,0, ar.length-1));


    }

}


